home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / pair.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  17.2 KB  |  667 lines  |  [TEXT/R*ch]
  1. #include "espresso.h"
  2.  
  3. void set_pair(PLA)
  4. pPLA PLA;
  5. {
  6.     set_pair1(PLA, TRUE);
  7. }
  8.  
  9. void set_pair1(PLA, adjust_labels)
  10. pPLA PLA;
  11. bool adjust_labels;
  12. {
  13.     int i, var, *paired, newvar;
  14.     int old_num_vars, old_num_binary_vars, old_size, old_mv_start;
  15.     int *new_part_size, new_num_vars, new_num_binary_vars, new_mv_start;
  16.     ppair pair = PLA->pair;
  17.     char scratch[1000], **oldlabel, *var1, *var1bar, *var2, *var2bar;
  18.  
  19.     if (adjust_labels)
  20.     makeup_labels(PLA);
  21.  
  22.     /* Check the pair structure for valid entries and see which binary
  23.     variables are left unpaired
  24.     */
  25.     paired = ALLOC(bool, cube.num_binary_vars);
  26.     for(var = 0; var < cube.num_binary_vars; var++)
  27.     paired[var] = FALSE;
  28.     for(i = 0; i < pair->cnt; i++)
  29.     if ((pair->var1[i] > 0 && pair->var1[i] <= cube.num_binary_vars) &&
  30.          (pair->var2[i] > 0 && pair->var2[i] <= cube.num_binary_vars)) {
  31.         paired[pair->var1[i]-1] = TRUE;
  32.         paired[pair->var2[i]-1] = TRUE;
  33.     } else
  34.         fatal("can only pair binary-valued variables");
  35.  
  36.     PLA->F = delvar(pairvar(PLA->F, pair), paired);
  37.     PLA->R = delvar(pairvar(PLA->R, pair), paired);
  38.     PLA->D = delvar(pairvar(PLA->D, pair), paired);
  39.  
  40.     /* Now painfully adjust the cube size */
  41.     old_size = cube.size;
  42.     old_num_vars = cube.num_vars;
  43.     old_num_binary_vars = cube.num_binary_vars;
  44.     old_mv_start = cube.first_part[cube.num_binary_vars];
  45.     /* Create the new cube.part_size vector and setup the cube structure */
  46.     new_num_binary_vars = 0;
  47.     for(var = 0; var < old_num_binary_vars; var++)
  48.     new_num_binary_vars += (paired[var] == FALSE);
  49.     new_num_vars = new_num_binary_vars + pair->cnt;
  50.     new_num_vars += old_num_vars - old_num_binary_vars;
  51.     new_part_size = ALLOC(int, new_num_vars);
  52.     for(var = 0; var < pair->cnt; var++)
  53.     new_part_size[new_num_binary_vars + var] = 4;
  54.     for(var = 0; var < old_num_vars - old_num_binary_vars; var++)
  55.     new_part_size[new_num_binary_vars + pair->cnt + var] =
  56.         cube.part_size[old_num_binary_vars + var];
  57.     setdown_cube();
  58.     FREE(cube.part_size);
  59.     cube.num_vars = new_num_vars;
  60.     cube.num_binary_vars = new_num_binary_vars;
  61.     cube.part_size = new_part_size;
  62.     cube_setup();
  63.  
  64.     /* hack with the labels to get them correct */
  65.     if (adjust_labels) {
  66.     oldlabel = PLA->label;
  67.     PLA->label = ALLOC(char *, cube.size);
  68.     for(var = 0; var < pair->cnt; var++) {
  69.         newvar = cube.num_binary_vars*2 + var*4;
  70.         var1 = oldlabel[ (pair->var1[var]-1) * 2 + 1];
  71.         var2 = oldlabel[ (pair->var2[var]-1) * 2 + 1];
  72.         var1bar = oldlabel[ (pair->var1[var]-1) * 2];
  73.         var2bar = oldlabel[ (pair->var2[var]-1) * 2];
  74.         (void) sprintf(scratch, "%s+%s", var1bar, var2bar);
  75.         PLA->label[newvar] = util_strsav(scratch);
  76.         (void) sprintf(scratch, "%s+%s", var1bar, var2);
  77.         PLA->label[newvar+1] = util_strsav(scratch);
  78.         (void) sprintf(scratch, "%s+%s", var1, var2bar);
  79.         PLA->label[newvar+2] = util_strsav(scratch);
  80.         (void) sprintf(scratch, "%s+%s", var1, var2);
  81.         PLA->label[newvar+3] = util_strsav(scratch);
  82.     }
  83.     /* Copy the old labels for the unpaired binary vars */
  84.     i = 0;
  85.     for(var = 0; var < old_num_binary_vars; var++) {
  86.         if (paired[var] == FALSE) {
  87.         PLA->label[2*i] = oldlabel[2*var];
  88.         PLA->label[2*i+1] = oldlabel[2*var+1];
  89.         oldlabel[2*var] = oldlabel[2*var+1] = (char *) NULL;
  90.         i++;
  91.         }
  92.     }
  93.     /* Copy the old labels for the remaining unpaired vars */
  94.     new_mv_start = cube.num_binary_vars*2 + pair->cnt*4;
  95.     for(i = old_mv_start; i < old_size; i++) {
  96.         PLA->label[new_mv_start + i - old_mv_start] = oldlabel[i];
  97.         oldlabel[i] = (char *) NULL;
  98.     }
  99.     /* free remaining entries in oldlabel */
  100.     for(i = 0; i < old_size; i++)
  101.         if (oldlabel[i] != (char *) NULL)
  102.         FREE(oldlabel[i]);
  103.     FREE(oldlabel);
  104.     }
  105.  
  106.     /* the paired variables should not be sparse (cf. mv_reduce/raise_in)*/
  107.     for(var = 0; var < pair->cnt; var++)
  108.     cube.sparse[cube.num_binary_vars + var] = 0;
  109.     FREE(paired);
  110. }
  111.  
  112. pcover pairvar(A, pair)
  113. pcover A;
  114. ppair pair;
  115. {
  116.     register pcube last, p;
  117.     register int val, p1, p2, b1, b0;
  118.     int insert_col, pairnum;
  119.  
  120.     insert_col = cube.first_part[cube.num_vars - 1];
  121.  
  122.     /* stretch the cover matrix to make room for the paired variables */
  123.     A = sf_delcol(A, insert_col, -4*pair->cnt);
  124.  
  125.     /* compute the paired values */
  126.     foreach_set(A, last, p) {
  127.     for(pairnum = 0; pairnum < pair->cnt; pairnum++) {
  128.         p1 = cube.first_part[pair->var1[pairnum] - 1];
  129.         p2 = cube.first_part[pair->var2[pairnum] - 1];
  130.         b1 = is_in_set(p, p2+1);
  131.         b0 = is_in_set(p, p2);
  132.         val = insert_col + pairnum * 4;
  133.         if (/* a0 */ is_in_set(p, p1)) {
  134.         if (b0)
  135.             set_insert(p, val + 3);
  136.         if (b1)
  137.             set_insert(p, val + 2);
  138.         }
  139.         if (/* a1 */ is_in_set(p, p1+1)) {
  140.         if (b0)
  141.             set_insert(p, val + 1);
  142.         if (b1)
  143.             set_insert(p, val);
  144.         }
  145.     }
  146.     }
  147.     return A;
  148. }
  149.  
  150.  
  151. /* delvar -- delete variables from A, minimize the number of column shifts */
  152. pcover delvar(A, paired)
  153. pcover A;
  154. bool paired[];
  155. {
  156.     bool run;
  157.     int first_run, run_length, var, offset = 0;
  158.  
  159.     run = FALSE; run_length = 0;
  160.     for(var = 0; var < cube.num_binary_vars; var++)
  161.     if (paired[var])
  162.         if (run)
  163.         run_length += cube.part_size[var];
  164.         else {
  165.         run = TRUE;
  166.         first_run = cube.first_part[var];
  167.         run_length = cube.part_size[var];
  168.         }
  169.     else
  170.         if (run) {
  171.         A = sf_delcol(A, first_run-offset, run_length);
  172.         run = FALSE;
  173.         offset += run_length;
  174.         }
  175.     if (run)
  176.     A = sf_delcol(A, first_run-offset, run_length);
  177.     return A;
  178. }
  179.  
  180. /*
  181.     find_optimal_pairing -- find which binary variables should be paired
  182.     to maximally reduce the number of terms
  183.  
  184.     This is essentially the technique outlined by T. Sasao in the
  185.     Trans. on Comp., Oct 1984.  We estimate the cost of pairing each
  186.     pair individually using 1 of 4 strategies: (1) algebraic division
  187.     of F by the pair (exactly T. Sasao technique); (2) strong division
  188.     of F by the paired variables (using REDUCE/EXPAND/ IRREDUNDANT from
  189.     espresso); (3) full minimization using espresso; (4) exact
  190.     minimization.  These are in order of both increasing accuracy and
  191.     increasing difficulty (!)
  192.  
  193.     Once the n squared pairs have been evaluated, T. Sasao proposes a
  194.     graph covering of nodes by disjoint edges.  For now, I solve this
  195.     problem exhaustively (complexity = (n-1)*(n-3)*...*3*1 for n
  196.     variables when n is even).  Note that solving this problem exactly
  197.     is the same as evaluating the cost function for all possible
  198.     pairings.
  199.  
  200.                    n       pairs
  201.  
  202.                  1, 2           1
  203.                  3, 4           3
  204.                  5, 6          15
  205.                  7, 8         105
  206.                  9,10         945
  207.                 11,12      10,395
  208.                 13,14     135,135
  209.                 15,16   2,027,025
  210.                 17,18  34,459,425
  211.                 19,20 654,729,075
  212. */
  213. void find_optimal_pairing(PLA, strategy)
  214. pPLA PLA;
  215. int strategy;
  216. {
  217.     int i, j, **cost_array;
  218.  
  219.     cost_array = find_pairing_cost(PLA, strategy);
  220.  
  221.     if (summary) {
  222.     printf("    ");
  223.     for(i = 0; i < cube.num_binary_vars; i++)
  224.         printf("%3d ", i+1);
  225.     printf("\n");
  226.     for(i = 0; i < cube.num_binary_vars; i++) {
  227.         printf("%3d ", i+1);
  228.         for(j = 0; j < cube.num_binary_vars; j++)
  229.         printf("%3d ", cost_array[i][j]);
  230.         printf("\n");
  231.     }
  232.     }
  233.  
  234.     if (cube.num_binary_vars <= 14) {
  235.     PLA->pair = pair_best_cost(cost_array);
  236.     } else {
  237.     (void) greedy_best_cost(cost_array, &(PLA->pair));
  238.     }
  239.     printf("# ");
  240.     print_pair(PLA->pair);
  241.     
  242.     for(i = 0; i < cube.num_binary_vars; i++)
  243.     FREE(cost_array[i]);
  244.     FREE(cost_array);
  245.  
  246.     set_pair(PLA);
  247.     EXEC_S(PLA->F=espresso(PLA->F,PLA->D,PLA->R),"ESPRESSO  ",PLA->F);
  248. }
  249.  
  250. int **find_pairing_cost(PLA, strategy)
  251. pPLA PLA;
  252. int strategy;
  253. {
  254.     int var1, var2, **cost_array;
  255.     int i, j, xnum_binary_vars, xnum_vars, *xpart_size, cost;
  256.     pcover T, Fsave, Dsave, Rsave;
  257.     pset mask;
  258. /*    char *s;*/
  259.  
  260.     /* data is returned in the cost array */
  261.     cost_array = ALLOC(int *, cube.num_binary_vars);
  262.     for(i = 0; i < cube.num_binary_vars; i++)
  263.     cost_array[i] = ALLOC(int, cube.num_binary_vars);
  264.     for(i = 0; i < cube.num_binary_vars; i++)
  265.     for(j = 0; j < cube.num_binary_vars; j++)
  266.         cost_array[i][j] = 0;
  267.  
  268.     /* Setup the pair structure for pairing variables together */
  269.     PLA->pair = pair_new(1);
  270.     PLA->pair->cnt = 1;
  271.  
  272.     for(var1 = 0; var1 < cube.num_binary_vars-1; var1++) {
  273.     for(var2 = var1+1; var2 < cube.num_binary_vars; var2++) {
  274.         /* if anything but simple strategy, perform setup */
  275.         if (strategy > 0) {
  276.         /* save the original covers */
  277.         Fsave = sf_save(PLA->F);
  278.         Dsave = sf_save(PLA->D);
  279.         Rsave = sf_save(PLA->R);
  280.  
  281.         /* save the original cube structure */
  282.         xnum_binary_vars = cube.num_binary_vars;
  283.         xnum_vars = cube.num_vars;
  284.         xpart_size = ALLOC(int, cube.num_vars);
  285.         for(i = 0; i < cube.num_vars; i++)
  286.             xpart_size[i] = cube.part_size[i];
  287.  
  288.         /* pair two variables together */
  289.         PLA->pair->var1[0] = var1 + 1;
  290.         PLA->pair->var2[0] = var2 + 1;
  291.         set_pair1(PLA, /* adjust_labels */ FALSE);
  292.         }
  293.  
  294.  
  295.         /* decide how to best estimate worth of this pairing */
  296.         switch(strategy) {
  297.         case 3:
  298.             /*s = "exact minimization";*/
  299.             PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1);
  300.             cost = Fsave->count - PLA->F->count;
  301.             break;
  302.         case 2:
  303.             /*s = "full minimization";*/
  304.             PLA->F = espresso(PLA->F, PLA->D, PLA->R);
  305.             cost = Fsave->count - PLA->F->count;
  306.             break;
  307.         case 1:
  308.             /*s = "strong division";*/
  309.             PLA->F = reduce(PLA->F, PLA->D);
  310.             PLA->F = expand(PLA->F, PLA->R, FALSE);
  311.             PLA->F = irredundant(PLA->F, PLA->D);
  312.             cost = Fsave->count - PLA->F->count;
  313.             break;
  314.         case 0:
  315.             /*s = "weak division";*/
  316.             mask = new_cube();
  317.             set_or(mask, cube.var_mask[var1], cube.var_mask[var2]);
  318.             T = dist_merge(sf_save(PLA->F), mask);
  319.             cost = PLA->F->count - T->count;
  320.             sf_free(T);
  321.             set_free(mask);
  322.         }
  323.  
  324.         cost_array[var1][var2] = cost;
  325.  
  326.         if (strategy > 0) {
  327.         /* restore the original cube structure -- free the new ones */
  328.         setdown_cube();
  329.         FREE(cube.part_size);
  330.         cube.num_binary_vars = xnum_binary_vars;
  331.         cube.num_vars = xnum_vars;
  332.         cube.part_size = xpart_size;
  333.         cube_setup();
  334.  
  335.         /* restore the original cover(s) -- free the new ones */
  336.         sf_free(PLA->F);
  337.         sf_free(PLA->D);
  338.         sf_free(PLA->R);
  339.         PLA->F = Fsave;
  340.         PLA->D = Dsave;
  341.         PLA->R = Rsave;
  342.         }
  343.     }
  344.     }
  345.  
  346.     pair_free(PLA->pair);
  347.     PLA->pair = NULL;
  348.     return cost_array;
  349. }
  350.  
  351. static int best_cost;
  352. static int **cost_array;
  353. static ppair best_pair;
  354. static pset best_phase;
  355. static pPLA global_PLA;
  356. static pcover best_F, best_D, best_R;
  357. static int pair_minim_strategy;
  358.  
  359.  
  360. print_pair(pair)
  361. ppair pair;
  362. {
  363.     int i;
  364.  
  365.     printf("pair is");
  366.     for(i = 0; i < pair->cnt; i++)
  367.     printf (" (%d %d)", pair->var1[i], pair->var2[i]);
  368.     printf("\n");
  369. }
  370.  
  371.  
  372. int greedy_best_cost(cost_array_local, pair_p)
  373. int **cost_array_local;
  374. ppair *pair_p;
  375. {
  376.     int i, j, besti, bestj, maxcost, total_cost;
  377.     pset cand;
  378.     ppair pair;
  379.  
  380.     pair = pair_new(cube.num_binary_vars);
  381.     cand = set_full(cube.num_binary_vars);
  382.     total_cost = 0;
  383.  
  384.     while (set_ord(cand) >= 2) {
  385.     maxcost = -1;
  386.     for(i = 0; i < cube.num_binary_vars; i++) {
  387.         if (is_in_set(cand, i)) {
  388.         for(j = i+1; j < cube.num_binary_vars; j++) {
  389.             if (is_in_set(cand, j)) {
  390.             if (cost_array_local[i][j] > maxcost) {
  391.                 maxcost = cost_array_local[i][j];
  392.                 besti = i;
  393.                 bestj = j;
  394.             }
  395.             }
  396.         }
  397.         }
  398.     }
  399.     pair->var1[pair->cnt] = besti+1;
  400.     pair->var2[pair->cnt] = bestj+1;
  401.     pair->cnt++;
  402.     set_remove(cand, besti);
  403.     set_remove(cand, bestj);
  404.     total_cost += maxcost;
  405.     }
  406.     set_free(cand);
  407.     *pair_p = pair;
  408.     return total_cost;
  409. }
  410.  
  411.  
  412. ppair pair_best_cost(cost_array_local)
  413. int **cost_array_local;
  414. {
  415.     ppair pair;
  416.     pset candidate;
  417.  
  418.     best_cost = -1;
  419.     best_pair = NULL;
  420.     cost_array = cost_array_local;
  421.  
  422.     pair = pair_new(cube.num_binary_vars);
  423.     candidate = set_full(cube.num_binary_vars);
  424.     generate_all_pairs(pair, cube.num_binary_vars, candidate, find_best_cost);
  425.     pair_free(pair);
  426.     set_free(candidate);
  427.     return best_pair;
  428. }
  429.  
  430.  
  431. int find_best_cost(pair)
  432. register ppair pair;
  433. {
  434.     register int i, cost;
  435.  
  436.     cost = 0;
  437.     for(i = 0; i < pair->cnt; i++)
  438.     cost += cost_array[pair->var1[i]-1][pair->var2[i]-1];
  439.     if (cost > best_cost) {
  440.     best_cost = cost;
  441.     best_pair = pair_save(pair, pair->cnt);
  442.     }
  443.     if ((debug & MINCOV) && trace) {
  444.     printf("cost is %d ", cost);
  445.     print_pair(pair);
  446.     }
  447. }
  448.  
  449. /*
  450.     pair_all: brute-force approach to try all possible pairings
  451.  
  452.     pair_strategy is:
  453.     2) for espresso
  454.     3) for minimize_exact
  455.     4) for phase assignment
  456. */
  457.  
  458. pair_all(PLA, pair_strategy)
  459. pPLA PLA;
  460. int pair_strategy;
  461. {
  462.     ppair pair;
  463.     pset candidate;
  464.  
  465.     global_PLA = PLA;
  466.     pair_minim_strategy = pair_strategy;
  467.     best_cost = PLA->F->count + 1;
  468.     best_pair = NULL;
  469.     best_phase = NULL;
  470.     best_F = best_D = best_R = NULL;
  471.     pair = pair_new(cube.num_binary_vars);
  472.     candidate = set_fill(set_new(cube.num_binary_vars), cube.num_binary_vars);
  473.  
  474.     generate_all_pairs(pair, cube.num_binary_vars, candidate, minimize_pair);
  475.  
  476.     pair_free(pair);
  477.     set_free(candidate);
  478.  
  479.     PLA->pair = best_pair;
  480.     PLA->phase = best_phase;
  481. /* not really necessary
  482.     if (phase != NULL)
  483.     (void) set_phase(PLA->phase);
  484. */
  485.     set_pair(PLA);
  486.     printf("# ");
  487.     print_pair(PLA->pair);
  488.  
  489.     sf_free(PLA->F);
  490.     sf_free(PLA->D);
  491.     sf_free(PLA->R);
  492.     PLA->F = best_F;
  493.     PLA->D = best_D;
  494.     PLA->R = best_R;
  495. }
  496.  
  497.  
  498. /*
  499.  *  minimize_pair -- called as each pair is generated
  500.  */
  501. int minimize_pair(pair)
  502. ppair pair;
  503. {
  504.     pcover Fsave, Dsave, Rsave;
  505.     int i, xnum_binary_vars, xnum_vars, *xpart_size;
  506.  
  507.     /* save the original covers */
  508.     Fsave = sf_save(global_PLA->F);
  509.     Dsave = sf_save(global_PLA->D);
  510.     Rsave = sf_save(global_PLA->R);
  511.  
  512.     /* save the original cube structure */
  513.     xnum_binary_vars = cube.num_binary_vars;
  514.     xnum_vars = cube.num_vars;
  515.     xpart_size = ALLOC(int, cube.num_vars);
  516.     for(i = 0; i < cube.num_vars; i++)
  517.     xpart_size[i] = cube.part_size[i];
  518.  
  519.     /* setup the paired variables */
  520.     global_PLA->pair = pair;
  521.     set_pair1(global_PLA, /* adjust_labels */ FALSE);
  522.  
  523.     /* call the minimizer */
  524.     if (summary)
  525.     print_pair(pair);
  526.     switch(pair_minim_strategy) {
  527.     case 2:
  528.         EXEC_S(phase_assignment(global_PLA,0), "OPO       ", global_PLA->F);
  529.         if (summary)
  530.         printf("# phase is %s\n", pc1(global_PLA->phase));
  531.         break;
  532.     case 1:
  533.         EXEC_S(global_PLA->F = minimize_exact(global_PLA->F, global_PLA->D,
  534.         global_PLA->R, 1), "EXACT     ", global_PLA->F);
  535.         break;
  536.     case 0:
  537.         EXEC_S(global_PLA->F = espresso(global_PLA->F, global_PLA->D,
  538.         global_PLA->R), "ESPRESSO  ", global_PLA->F);
  539.         break;
  540.     default:
  541.         break;
  542.     }
  543.  
  544.     /* see if we have a new best solution */
  545.     if (global_PLA->F->count < best_cost) {
  546.     best_cost = global_PLA->F->count;
  547.     best_pair = pair_save(pair, pair->cnt);
  548.     best_phase = global_PLA->phase!=NULL?set_save(global_PLA->phase):NULL;
  549.     if (best_F != NULL) sf_free(best_F);
  550.     if (best_D != NULL) sf_free(best_D);
  551.     if (best_R != NULL) sf_free(best_R);
  552.     best_F = sf_save(global_PLA->F);
  553.     best_D = sf_save(global_PLA->D);
  554.     best_R = sf_save(global_PLA->R);
  555.     }
  556.  
  557.     /* restore the original cube structure -- free the new ones */
  558.     setdown_cube();
  559.     FREE(cube.part_size);
  560.     cube.num_binary_vars = xnum_binary_vars;
  561.     cube.num_vars = xnum_vars;
  562.     cube.part_size = xpart_size;
  563.     cube_setup();
  564.  
  565.     /* restore the original cover(s) -- free the new ones */
  566.     sf_free(global_PLA->F);
  567.     sf_free(global_PLA->D);
  568.     sf_free(global_PLA->R);
  569.     global_PLA->F = Fsave;
  570.     global_PLA->D = Dsave;
  571.     global_PLA->R = Rsave;
  572.     global_PLA->pair = NULL;
  573.     global_PLA->phase = NULL;
  574. }
  575.  
  576. generate_all_pairs(pair, n, candidate, action)
  577. ppair pair;
  578. int n;
  579. pset candidate;
  580. int (*action)();
  581. {
  582.     int i, j;
  583.     pset recur_candidate;
  584.     ppair recur_pair;
  585.  
  586.     if (set_ord(candidate) < 2) {
  587.     (*action)(pair);
  588.     return;
  589.     }
  590.  
  591.     recur_pair = pair_save(pair, n);
  592.     recur_candidate = set_save(candidate);
  593.  
  594.     /* Find first variable still in the candidate set */
  595.     for(i = 0; i < n; i++)
  596.     if (is_in_set(candidate, i))
  597.         break;
  598.  
  599.     /* Try all pairs of i with other variables */
  600.     for(j = i+1; j < n; j++)
  601.     if (is_in_set(candidate, j)) {
  602.         /* pair (i j) -- remove from candidate set for future pairings */
  603.         set_remove(recur_candidate, i);
  604.         set_remove(recur_candidate, j);
  605.  
  606.         /* add to the pair array */
  607.         recur_pair->var1[recur_pair->cnt] = i+1;
  608.         recur_pair->var2[recur_pair->cnt] = j+1;
  609.         recur_pair->cnt++;
  610.  
  611.         /* recur looking for the end ... */
  612.         generate_all_pairs(recur_pair, n, recur_candidate, action);
  613.  
  614.         /* now break this pair, and restore candidate set */
  615.         recur_pair->cnt--;
  616.         set_insert(recur_candidate, i);
  617.         set_insert(recur_candidate, j);
  618.     }
  619.  
  620.     /* if odd, generate all pairs which do NOT include i */
  621.     if ((set_ord(candidate) % 2) == 1) {
  622.     set_remove(recur_candidate, i);
  623.     generate_all_pairs(recur_pair, n, recur_candidate, action);
  624.     }
  625.  
  626.     pair_free(recur_pair);
  627.     set_free(recur_candidate);
  628. }
  629.  
  630. ppair pair_new(n)
  631. register int n;
  632. {
  633.     register ppair pair1;
  634.  
  635.     pair1 = ALLOC(pair_t, 1);
  636.     pair1->cnt = 0;
  637.     pair1->var1 = ALLOC(int, n);
  638.     pair1->var2 = ALLOC(int, n);
  639.     return pair1;
  640. }
  641.  
  642.  
  643. ppair pair_save(pair, n)
  644. register ppair pair;
  645. register int n;
  646. {
  647.     register int k;
  648.     register ppair pair1;
  649.  
  650.     pair1 = pair_new(n);
  651.     pair1->cnt = pair->cnt;
  652.     for(k = 0; k < pair->cnt; k++) {
  653.     pair1->var1[k] = pair->var1[k];
  654.     pair1->var2[k] = pair->var2[k];
  655.     }
  656.     return pair1;
  657. }
  658.  
  659.  
  660. int pair_free(pair)
  661. register ppair pair;
  662. {
  663.     FREE(pair->var1);
  664.     FREE(pair->var2);
  665.     FREE(pair);
  666. }
  667.